package com.tgy.dynamic.programming;

import lombok.Data;

import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-11-16 14:16
 */
@Data
class Cargo {

    private int weight;
    private int value;

    public Cargo(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }

}

public class KnapsackChoice {

    public int maxValue(Cargo[] cargos, int maxWeight) {

        if (Objects.isNull(cargos) || cargos.length == 0 || maxWeight <= 0) {

            return 0;
        }

        /**
         * 最大承重为 i 时，能装的最大价值的cargo数量dp[i] ,其中i取值 【1,maxWeight]
         */
        int[] dp = new int[maxWeight + 1];

        for (Cargo cargo : cargos) {

            for (int i = maxWeight; i >= cargo.getWeight(); i--) {

                dp[i] = Math.max(dp[i],cargo.getValue() + dp[i - cargo.getWeight()]);
            }
//            System.out.print(cargo + ":  ");
//            for (int d : dp) {
//
//                System.out.print(d + ",");
//            }
//            System.out.println();
        }

        return dp[maxWeight];
    }
}
